The present invention relates to the field of communications in general, and more particularly to network communications.
Network switches (switches) may provide for the transmission of data from inputs of the switch to outputs of the switch. For example, a switch having N inputs and N outputs (an Nxc3x97N switch) may provide connectivity between any of the N inputs and any of the N outputs. Data received on an input can typically be switched to any of the outputs of the switch.
FIG. 1 is a block diagram which illustrates a 2Nxc3x972N switch that uses 4 Nxc3x97N switch elements to allow data received at any of the switch""s 2N input ports to be switched to any of switch""s 2N output ports. In particular, first through fourth switch elements 100a-d provide switching wherein data received on any of the input ports 1-2N can be switched to any number of the output ports 1-2N. For example, data received at input port 1 can be switched to the Output ports 1 to N through the first switch element 100a and/or to the output ports N+1 to 2N through the second switch element 100b. Similarly, data received at input port N+1 can be switched to output ports 1 to N through the third switch element 100c and/or to the output ports N+1 to 2N through the fourth switch element 100d. According to FIG. 1, the switch elements can represent separate integrated circuit devices.
Data received at the input ports 1-2N can typically be directed to any combination of the output ports 1-2N. For example, data received at input port 1 may be directed to a single output port or to all of the output ports. Furthermore, data received at more than one input port can be directed to a common output port. For example, data that is to be directed to output port 1 can be received at all input ports 1-2N. Moreover, the data can be received simultaneously. Consequently, each of the output ports has an associated queue that can be used to store data directed to that output port until the output port is available for transmission. Thus, a switch having N output ports can have N queues (one queue associated with each output port).
Additional switch elements can be added to the switch to increase the amount of data that the switch can process. For example, an Nxc3x97N switch can be expanded to a 2Nxc3x972N switch by quadrupling the number of switch elements. For example, according to FIG. 1, the first switch element 100a may be used to implement an Nxc3x97N switch. To expand the switch to 2Nxc3x972N, four switch elements are needed (i.e., the relationship between the number of input and outputs that can be switched and the number of switch elements can be quadratic). Moreover, as more switch elements are added, more switch elements may need to be coordinated during transmission of data from the output ports. For example, both the first switch element 100a and the third switch element 100c can transmit data onto output port 1. Accordingly, the transmission of data by the first and third switch elements 110a, c may need to be coordinated to reduce the likelihood of contentions on the output ports which they share.
A centralized queue control circuit 105 can control which of the switch elements may transmit. For example, if two streams of data each directed to the output port 1 are received at input port 1 and input port N+1 respectively, the centralized queue control circuit 105 controls when the first switch element 110a transmits on the output port 1 and when the third switch element 100c transmits data on the output port 1. Accordingly, the centralized queue control circuit 105 may first enable the first switch element 100a to transmit on the output port 1 and then enable the third switch element 100c to transmit on the output port 1. The centralized queue control circuit 105 can xe2x80x9cping-pongxe2x80x9d between enabling the first and third switch elements to switch the two streams of data to the output port 1. Unfortunately, the xe2x80x9cping-pongxe2x80x9d approach described above may result in an uneven or xe2x80x9cunfairxe2x80x9d allocation of the output port bandwidth among the switch elements used to switch the data to the desired output port. In particular, if a first switch element receives data directed to an output port at more input ports than does a second switch element, the bandwidth allocated to the first switch element can be divided among more input ports. Consequently, the bandwidth available to each of the input ports of the first switch element is a fraction of the total bandwidth allocated to the first switch element. For example, if data directed to output port 1, is received at input ports 1 to N of the first switch element 100a and at input-port N+1 of the third switch element 100c, the first switch element 100a will queue data received at input ports 1 to N while the third switch element 100c will queue data received at input port N+1.
The centralized queue control circuit 105 can alternatingly select the first switch element 100a and the third switch element 100c for transmission therefrom. Alternating between the first and third switch elements 100a, c may result in 50% of the output port bandwidth being allocated to the each of the switch elements. For a switch element of size N=16 this may result in input ports 1-16 each obtaining approximately 3% of the output port bandwidth while input port 17 receives 50% of the bandwidth. Accordingly, there continues to exist a need to provide queued memory switches that can be expanded while maintaining fairness thereof without adding undue complexity to the associated control logic.
The present invention can provide methods, switches, systems, and computer program products that allow improved fairness in queued memory switches when devices are added to the queued memory switch to increase the capacity thereof by enabling the devices to transmit the data in the order in which the data was received.
In one embodiment of the present invention, first and second data are received at first and second inputs of first and second devices included in the queued memory switch. The first and second data are directed to the same output of the queued memory switch. An indication is made of the order of reception of the first and second data at the first and second devices. The first and second data are transmitted from the output of the queued memory switch in the indicated order of reception. Therefore, the unfair distribution of output port bandwidth associated with some conventional systems described above, may be reduced by enabling the devices to transmit the data in the order in which the data was received.
In another embodiment of the present invention, the first and second data are respective first and second cells of data. Alternatively, the first and second data may be respective first and second frames of data.
In yet another embodiment of the present invention, the indication includes a series of indications of the reception of the first and second data at a series of reception times.
In a still further embodiment of the present invention, the indication includes indicating reception of the first data and non-reception of the second data if the first data is received at a reception time and the second data is not received at each reception time. Alternatively, the indication includes indicating non-reception of the first data and reception of the second data if the second data is received at the reception time and the first data is not received at each reception time. Finally, the indication may include indicating the reception of the first data and reception of the second data if the first and second data are received at each reception time.
In still another aspect of the present invention, the indication includes storing a first indication of the reception of the first data at each reception time and storing a second indication of the reception of the second data at each reception time.
In another aspect of the present invention, the data is transmitted by determining that the output of the queued memory switch is available for data transmission, and transmitting a grant from the first device to the second device in response to the indication that the first and second data were received at the reception time, and transmitting the second data from the second device on the output of the queued memory device responsive to the grant.